The present invention includes two distinct aspects which are preferably used together. The first aspect relates to a method to find polygons which uses data from the corners of polygons. The second aspect relates to search tree for a geometric match wherein search tree segments are truncated or pruned. The preferred embodiment of the invention relates to locating polygons based on corner data using the inventive geometric matching technique.
The manufacture of integrated circuit chips rely on high speed manufacturing processes which typically incorporate systems which inspect the chips or provide a reference location on the chips. Such systems include cameras which capture images of the chips and controllers or computers which are operative to locate objects within the images. Objects are located or inspected to either approve the quality and configuration of a part or direct some aspect of the manufacturing process.
Many different techniques have been developed to locate objects within images. Many popular techniques involve correlation. There are several types of correlation methods including convolution, normalized correlation, least mean squares error and least mean absolute error. Correlation requires the definition of a template or kernel which is a separate small image with the same shape as the object to be located. Like the object, the template may be represented by spatial coordinate points with a brightness for each value. These spatial points are commonly referred to as pixels. The template is moved across the image and correlated against the image to determine a match. Correlation techniques are often used because they can locate an object within an image in a comparatively short period of time. One of the fastest and most accurate correlation techniques in the marketplace is binary vector correlation. The theory behind binary vector correlation is covered in a paper entitled xe2x80x9cVector Morphology and Iconic Neural Networksxe2x80x9d by S. S. Wilson in IEEE Transactions on Systems Man, and Cybernetics, November/December, 1989 Vol. 19, nol 6, pp. 1636-1644. Correlation techniques have improved as disclosed in commonly assigned U.S. Pat. No. 6,023,530.
While correlation techniques are comparatively fast, one problem with many correlation techniques is that they are rotationally and scale intolerant. Rotational intolerance describes the situation where the relative angle of the object within the image, as measured from a Cartesian axis, is different from the angle of the template as measured from the same Cartesian axis. An example of this would be a square and a diamond with equal length sides and corner angles of ninety degrees. Scale intolerance problems created when the template is a different size compared to the object. Thus, correlation techniques are not particularly useful in finding rotated objects.
An example of where correlation techniques have been successfully used is in the semiconductor industry to locate pads on integrated circuit chips. Pads provide the interconnection interface to device or other circuitry and need to be accurately located before probing and bonding. In the past, the pad was square or rectangular in shape. However, as chip design has advanced pad shapes have changed and have rotated. Thus, prior art correlation techniques are not particularly well suited to certain advancements in the manufacturing of integrated circuit chips.
Also in pick and place operations, chip components are picked from a tray, inspected and then placed to be soldered on a printed circuit board. The picked component may be rotated or offset from an expected position and it is necessary to use a vision system to find its orientation, the correct size and potentially inspect it in order for it to be placed correctly on the board. In another aspect of this process, a vision system may be used to locate fiducials or registration marks on the circuit boards in order to find the location and orientation of the board before chip components are placed.
An image processing techniques which has been used to locate rotated objects is geometric matching. Geometric matching describes the process of comparing individual geometric features from a model against geometric features extracted from an image to locate an object within the image. For example, the geometric features from a model may be the length, location and direction of a pattern of line segments. A geometric matching technique would extract line segments from an input image and compare each extracted line segment against the collection of predefined geometric features to locate an object within an image.
Many types of geometric matches are available in the prior art. These include key feature algorithms; generalized Hough algorithms; search trees and geometric hashing. Key feature algorithms search for a small number of highly distinctive local geometric features which indicate the placement of an object in an image. Generalized Hough algorithms employ voting schemes to search all possibilities in a pose space. Tree search algorithms expand a tree of potential matches between a model and image features using local geometric consistencies constraints for pruning. Geometric hashing first creates a hash table of all subsets of image features and then at run time selects sets of data features within an acquired image and looks up their correspondence in the hash table. These prior art techniques are described in an article entitled xe2x80x9cLocal Search Algorithms for Geometric Object Recognition: Optimal Correspondence and Pose, J. Ross Beveridge, University of Massachusetts at Amherst, Ph.D. Dissertation, June 1993, (Also UM Mass Techreport 93-71), which is incorporated herein by reference.
Of the many prior art techniques, tree searches examine the most features and is thus the most computationally intensive. Because of the enormous amount of data which may be compared the search tree and other geometric matching techniques are often slow.
Because of its comparatively slower speed to provide high accuracy, geometric matches are not always well suited to the requirements of the integrated circuit chips industry. Therefore a need has arisen to provide a method to quickly locate an object within an image where the object is rotated.
The first aspect of the present invention provides for a method for locating a polygon within an image using a polygon model defined by corner features. An image is captured and corner features are extracted from the image. A geometric match is used to compare the corner features from the polygon model against the corner features extracted from the image to locate a polygon within the image that matches the polygon model.
In a preferred embodiment of the first aspect of the present invention, line edge segments are extracted from the input image and it is determined whether the line edge segments define corners. Corners are formed from the line edge segments where the line segments define corners.
A further aspect of the preferred embodiment of the first aspect of the present invention locates polygons using a search tree including comparing the corner features from the model against the plurality of corners features extracted from the image, calculating a pose and calculating fit errors and match score for each of the comparisons, and; truncating the search tree if the pose fit errors and match score fall outside predefined parameters.
The first aspect of the present invention also provides for an article of manufacture including a computer readable medium bearing computer program code embodied therein for performing a task. The computer readable medium includes means for defining a polygon model defined by corner features, means for activating a camera to capture an image of an object wherein the image includes a polygon, means for extracting corner features from the image, and means for geometrically matching the corner features from the polygon model against the corner features extracted from the image to locate a polygon within the image that matches the polygon model.
A second aspect of the present invention provides for a pruned tree search including providing a model of the object including a plurality of geometric model features and an input image. A plurality of geometric features are extracted from the input image where the geometric features are of the same quality of the geometric model features. A first geometric model feature is compared against the plurality of extracted geometric features and the first geometric model feature is matched against a first extracted geometric feature if their comparison falls within predefined local consistency measures to thereby form a first branch within the search tree. A second geometric model feature is compared against the plurality of extracted geometric features and the second geometric model feature is matched against a second extracted feature if their comparison falls within predefined local consistency measures to thereby form a second branch within the search tree which depends from the first branch. A third geometric model feature is matched against the plurality of extracted geometric features and a provisional match is found between the third geometric model feature and a third extracted geometric feature. A pose is calculated based on the comparison of the first through third model features and extracted features, and the provisional match is not accepted if the pose falls outside a predefined pose bound.
A preferred embodiment of the second aspect of the present invention involves transforming the model features based on the calculated pose and calculating fit errors based on the difference between the pose-transformed model and the matched features location. The provisional match is not accepted if the fit errors fall outside the maximum defined fit errors.
A further preferred embodiment of the present invention allows the geometric match to minimize fit error or maximize the number of matches. If the fit error is minimized the search tree is constructed with a minimum number of matched features wherein the minimum number of matched features is less than the plurality of geometric features. If the match is set to maximize the number of matched features the search tree is constructed such that a required number of matches is that all of the geometric features are matched against extracted geometric features.
The second aspect of the present invention also provides a computer readable storage medium containing software executable by a computer to perform process steps for performing a geometric match to locate an object within a captured image utilizing a model of the object, wherein the model includes a plurality geometric features. The process steps include extracting a plurality of geometric features from the input image of the same quality of the geometric model features. A first geometric model feature is compared against the plurality of extracted geometric features and the first geometric model feature is matched against a first extracted geometric feature if their comparison falls within predefined local consistency measures to thereby form a first branch within the search tree. A second geometric model feature is compared against the plurality of extracted geometric features and the second geometric model feature is matched against a second extracted feature if their comparison falls within predefined local consistency measures to thereby form a second branch within the search tree which depends from the first branch. A third geometric model feature is matched against the plurality of extracted geometric features and a provisional match is found between the third geometric model feature and a third extracted geometric feature. A pose is calculated based on the comparison of the first through third model features and extracted features, and the provisional match is not accepted if the pose falls outside a predefined pose bound.
The computer readable storage medium may also be configured to carry out the process steps of transforming the model features based on the calculated pose, match score and calculating fit errors based on the difference between the pose-transformed model and the matched features location. The provisional match is not accepted if the fit errors fall outside the maximum defined fit errors.
In the preferred embodiment the first and second aspects of the present invention are used together. In particular, the preferred method of locating a polygon in an image including providing a polygon model including a plurality of model features where each model feature characteristic of a corner from the polygon. An input image is also provided and a plurality of corner features are extracted from the input image. A first model feature is compared against the plurality of extracted corner features and the first model feature is matched against a first extracted corner feature if their comparison falls within predefined local consistency measures to thereby form a first branch within a search tree. A second model feature is compared against the plurality of extracted corner features an the second model feature is matched against a second extracted corner feature if their comparison falls within predefined local consistency measures to thereby form a second branch within the search tree which depends from the first branch. A third geometric model feature is compared against the plurality of extracted corner features and a provisional match is found between the third geometric model feature and a third extracted corner feature. A pose is calculated based on the comparison of the first through third model features and extracted corner features but the provisional match is not accepted if the pose falls outside a predefined pose bound.
The preferred embodiment of the first and second aspect of the present invention involves transforming the model features based on the calculated pose and calculating fit errors based on the difference between the pose-transformed model and the matched features location. The provisional match is not accepted if the fit errors fall outside the maximum defined fit errors.